package demo8;

public class MagicIndex {

    public boolean findMagicIndex(int[] arr,int n){
        if (n==arr.length)return false;
        if(arr[n]==n){
            System.out.println("findMagicIndex is " +n);
            return true;
        }
        if(findMagicIndex(arr,n+1)){
            return true;
        };
        return false;
    }

    public int findMagicIndexFaster(int[] arr){
        // 0,5
        return binarySearch(arr,0,arr.length-1);

    }
    public int binarySearch(int[] arr , int low,int high){
        if(low>high){
            return -1;
        }
        int mid = (low + high )/2;
        if(arr[mid]==mid){
            return mid;
        } else if(arr[mid]>mid){
            return binarySearch(arr,low,mid-1);
        }else{
            // 3,5
            return binarySearch(arr,mid+1,high);
        }
    }
    public FindMagicIndexFasterWithDuplicate createFindMagicIndexFasterWithDuplicate(){
        return new FindMagicIndexFasterWithDuplicate();
    }
    /** 只可以正序，不允许负整数，
     * i:    0 1 2 3 4 5 6 7
       val:  0,0,1,2,3,6,7,7
     * val:  0,1,3,4 5 6 7 8
       val:  0 0 0 1 4 4 7
       val:  0 0 0 5 6 7 8  search right: (5,6)
     * val: -1 0 1 2 4 7 7
     */
    public class FindMagicIndexFasterWithDuplicate{
        public int findMagicIndexFasterWithDuplicate(int[] arr){
            return binarySearch(arr,0,arr.length-1);

        }
        public int binarySearch(int[] arr , int low,int high){
            if(low>high){
                return -1;
            }
            int mid = (low + high )/2;
            if(arr[mid]==mid){
                return mid;
            }
            // search left
            int leftmid=Math.min(mid-1,arr[mid]);
            int left = binarySearch(arr,low,leftmid);
            if (left>=0) {
                return left;
            }
            // search right
            int rightmid=Math.max(mid+1,arr[mid]);
            int right=binarySearch(arr,rightmid,high);
            return right;

        }
    }
}
